/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Answer:6857
Time:176ms
*/

package main

import (
	"fmt"
	"time"
)

// m 存放质数
var m = make(map[int]bool)

func main() {
	tstart := time.Now()
	n := 600851475143
	for i := 2; ; i++ {
		if prime(i) {
			for n%i == 0 {
				n /= i
			}
			if n == 1 {
				fmt.Println(i)
				break
			}
		}
	}
	tend := time.Now()
	fmt.Println(tend.Sub(tstart))
}

// prime 判断是否是质数，并将质数写入map
func prime(n int) bool {
	if !m[n] {
		if n < 2 {
			return false
		}
		if n < 3 {
			m[n] = true
			return true
		}
		prime(n - 1)
		for v := range m {
			if n%v == 0 {
				return false
			}
		}
		m[n] = true
	}
	return true
}
